home *** CD-ROM | disk | FTP | other *** search
/ Just Call Me Internet / Just Call Me Internet.iso / prog / atari / c / nos042_s / iproute.c < prev    next >
C/C++ Source or Header  |  1994-09-16  |  20KB  |  755 lines
  1. /* Lower half of IP, consisting of gateway routines
  2.  * Includes routing and options processing code
  3.  *
  4.  * Copyright 1991 Phil Karn, KA9Q
  5.  */
  6.  
  7. /****************************************************************************
  8. *    $Id: iproute.c 1.3 93/07/16 11:45:51 ROOT_DOS Exp $
  9. *    14 Jun 93    1.3        GT    Fix warnings.                                    *
  10. *                        GT    Fix ICMP_QUENCH.                                *
  11. *
  12. *  ATARI Version by David Nash - dnash@chaos.demon.co.uk
  13. *
  14. *  add hash_ip function
  15. *
  16. ****************************************************************************/
  17.  
  18. #include "global.h"
  19. #include "mbuf.h"
  20. #include "iface.h"
  21. #include "timer.h"
  22. #include "internet.h"
  23. #include "ip.h"
  24. #include "netuser.h"
  25. #include "icmp.h"
  26. #include "rip.h"
  27. #include "trace.h"
  28. #include "pktdrvr.h"
  29. #include "bootp.h"
  30. #include "filter.h"
  31.  
  32.  
  33. struct route *Routes[32][HASHMOD];    /* Routing table */
  34. struct route R_default = {        /* Default route entry */
  35.     NULLROUTE, NULLROUTE,
  36.     0,0,0,
  37.     RIP_INFINITY        /* Init metric to infinity */
  38. };
  39.  
  40. static struct rt_cache Rt_cache;
  41.  
  42. /* Initialize modulo lookup table used by hash_ip() in pcgen.asm */
  43. void
  44. ipinit()
  45. {
  46. #ifndef ATARI
  47.     int i;
  48.  
  49.     for(i=0;i<256;i++)
  50.         Hashtab[i] = i % HASHMOD;
  51. #endif        
  52. }
  53.  
  54. /*
  55.     hash_ip - Compute hash function on IP address
  56. */
  57.  
  58. int16 hash_ip(int32 addr)
  59. {
  60.     int16 ret;
  61.  
  62.     ret = hiword(addr);
  63.     ret ^= loword(addr);
  64.     return (int16)(ret % HASHMOD);
  65. }
  66.  
  67. /* Route an IP datagram. This is the "hopper" through which all IP datagrams,
  68.  * coming or going, must pass.
  69.  *
  70.  * "rxbroadcast" is set to indicate that the packet came in on a subnet
  71.  * broadcast. The router will kick the packet upstairs regardless of the
  72.  * IP destination address.
  73.  */
  74. int
  75. ip_route(i_iface,bp,rxbroadcast)
  76. struct iface *i_iface;    /* Input interface */
  77. struct mbuf *bp;    /* Input packet */
  78. int rxbroadcast;    /* True if packet had link broadcast address */
  79. {
  80.     struct ip ip;            /* IP header being processed */
  81.     int16 ip_len;            /* IP header length */
  82.     int16 length;            /* Length of data portion */
  83.     int32 gateway;            /* Gateway IP address */
  84.     register struct route *rp;    /* Route table entry */
  85.     struct iface *iface;        /* Output interface, possibly forwarded */
  86.     int16 offset;            /* Offset into current fragment */
  87.     int16 mf_flag;            /* Original datagram MF flag */
  88.     int strict = 0;            /* Strict source routing flag */
  89.     char prec;            /* Extracted from tos field */
  90.     char del;
  91.     char tput;
  92.     char rel;
  93.     int16 opt_len;        /* Length of current option */
  94.     char *opt;        /* -> beginning of current option */
  95.     int i;
  96.     struct mbuf *tbp;
  97.     int ckgood = IP_CS_OLD; /* Has good checksum without modification */
  98.     int pointer;        /* Relative pointer index for sroute/rroute */
  99.  
  100.     if(i_iface != NULLIF){
  101.         ipInReceives++;    /* Not locally generated */
  102.         i_iface->iprecvcnt++;
  103.     }
  104.     if(len_p(bp) < IPLEN){
  105.         /* The packet is shorter than a legal IP header */
  106.         ipInHdrErrors++;
  107.         free_p(bp);
  108.         return -1;
  109.     }
  110.     /* Sneak a peek at the IP header's IHL field to find its length */
  111.     ip_len = (bp->data[0] & 0xf) << 2;
  112.     if(ip_len < IPLEN){
  113.         /* The IP header length field is too small */
  114.         ipInHdrErrors++;
  115.         free_p(bp);
  116.         return -1;
  117.     }
  118.     if(cksum(NULLHEADER,bp,ip_len) != 0){
  119.         /* Bad IP header checksum; discard */
  120.         ipInHdrErrors++;
  121.         free_p(bp);
  122.         return -1;
  123.     }
  124.     /* Extract IP header */
  125.     ntohip(&ip,&bp);
  126.  
  127.     if(ip.version != IPVERSION){
  128.         /* We can't handle this version of IP */
  129.         ipInHdrErrors++;
  130.         free_p(bp);
  131.         return -1;
  132.     }
  133.     /* Trim data segment if necessary. */
  134.     length = ip.length - ip_len;    /* Length of data portion */
  135.     trim_mbuf(&bp,length);    
  136.                 
  137.     /* If we're running low on memory, return a source quench */
  138.     if (!rxbroadcast &&
  139.         availmem () < (Memthresh * 2) &&
  140.         availmem () > (Memthresh / 2))
  141.         icmp_output (&ip,bp,ICMP_QUENCH,0,NULLICMP);
  142.  
  143.     /* Process options, if any. Also compute length of secondary IP
  144.      * header in case fragmentation is needed later
  145.      */
  146.     strict = 0;
  147.     for(i=0;i<ip.optlen;i += opt_len){
  148.  
  149.         /* First check for the two special 1-byte options */
  150.         switch(ip.options[i] & OPT_NUMBER){
  151.         case IP_EOL:
  152.             goto no_opt;    /* End of options list, we're done */
  153.         case IP_NOOP:
  154.             opt_len = 1;
  155.             continue;    /* No operation, skip to next option */
  156.         }
  157.         /* Not a 1-byte option, so ensure that there's at least
  158.          * two bytes of option left, that the option length is
  159.          * at least two, and that there's enough space left for
  160.          * the specified option length.
  161.          */
  162.         if(ip.optlen - i < 2
  163.          || ((opt_len = uchar(ip.options[i+1])) < 2)
  164.          || ip.optlen - i < opt_len){
  165.             /* Truncated option, send ICMP and drop packet */
  166.             if(!rxbroadcast){
  167.                 union icmp_args icmp_args;
  168.  
  169.                 icmp_args.pointer = IPLEN + i;
  170.                 icmp_output(&ip,bp,ICMP_PARAM_PROB,0,&icmp_args);
  171.             }
  172.             free_p(bp);
  173.             return -1;
  174.         }
  175.         opt = &ip.options[i];
  176.  
  177.         switch(opt[0] & OPT_NUMBER){
  178.         case IP_SSROUTE:    /* Strict source route & record route */
  179.             strict = 1;    /* note fall-thru */
  180.         case IP_LSROUTE:    /* Loose source route & record route */
  181.             /* Source routes are ignored unless we're in the
  182.              * destination field
  183.              */
  184.             if(opt_len < 3){
  185.                 /* Option is too short to be a legal sroute.
  186.                  * Send an ICMP message and drop it.
  187.                  */
  188.                 if(!rxbroadcast){
  189.                     union icmp_args icmp_args;
  190.  
  191.                     icmp_args.pointer = IPLEN + i;
  192.                     icmp_output(&ip,bp,ICMP_PARAM_PROB,0,&icmp_args);
  193.                 }
  194.                 free_p(bp);
  195.                 return -1;
  196.             }
  197.             if(ismyaddr(ip.dest) == NULLIF)
  198.                 break;    /* Skip to next option */
  199.             pointer = uchar(opt[2]);
  200.             if(pointer + 4 > opt_len)
  201.                 break;    /* Route exhausted; it's for us */
  202.  
  203.             /* Put address for next hop into destination field,
  204.              * put our address into the route field, and bump
  205.              * the pointer. We've already ensured enough space.
  206.              */
  207.             ip.dest = get32(&opt[pointer]);
  208.             put32(&opt[pointer],locaddr(ip.dest));
  209.             opt[2] += 4;
  210.             ckgood = IP_CS_NEW;
  211.             break;
  212.         case IP_RROUTE:    /* Record route */
  213.             if(opt_len < 3){
  214.                 /* Option is too short to be a legal rroute.
  215.                  * Send an ICMP message and drop it.
  216.                  */
  217.                 if(!rxbroadcast){
  218.                     union icmp_args icmp_args;
  219.  
  220.                     icmp_args.pointer = IPLEN + i;
  221.                     icmp_output(&ip,bp,ICMP_PARAM_PROB,0,&icmp_args);
  222.                 }
  223.                 free_p(bp);
  224.                 return -1;
  225.             }                
  226.             pointer = uchar(opt[2]);
  227.             if(pointer + 4 > opt_len){
  228.                 /* Route area exhausted; send an ICMP msg */
  229.                 if(!rxbroadcast){
  230.                     union icmp_args icmp_args;
  231.  
  232.                     icmp_args.pointer = IPLEN + i;
  233.                     icmp_output(&ip,bp,ICMP_PARAM_PROB,0,&icmp_args);
  234.                 }
  235.                 /* Also drop if odd-sized */
  236.                 if(pointer != opt_len){
  237.                     free_p(bp);
  238.                     return -1;
  239.                 }
  240.             } else {
  241.                 /* Add our address to the route.
  242.                  * We've already ensured there's enough space.
  243.                  */
  244.                 put32(&opt[pointer],locaddr(ip.dest));
  245.                  opt[2] += 4;
  246.                 ckgood = IP_CS_NEW;
  247.             }
  248.             break;
  249.         }
  250.     }
  251. no_opt:
  252.  
  253. #ifdef FILTER
  254.     /*
  255.      *  If packet did not originate locally and an input filter
  256.      *  is specified on the input interface then apply it.
  257.      */
  258.     if ( i_iface != NULLIF && i_iface->infilter &&
  259.          ip_filter( bp, &ip, i_iface->infilter ) ) {
  260.         icmp_output(&ip,bp,ICMP_DEST_UNREACH,ICMP_HOST_UNREACH,NULLICMP);
  261.         free_p( bp );
  262.         return -1;
  263.     }
  264. #endif
  265.  
  266.     /* See if it's a broadcast or addressed to us, and kick it upstairs */
  267.     if(ismyaddr(ip.dest) != NULLIF || rxbroadcast ||
  268.         (WantBootp && bootp_validPacket(&ip, &bp))){
  269. #ifdef    GWONLY
  270.     /* We're only a gateway, we have no host level protocols */
  271.         if(!rxbroadcast)
  272.             icmp_output(&ip,bp,ICMP_DEST_UNREACH,
  273.              ICMP_PROT_UNREACH,NULLICMP);
  274.         ipInUnknownProtos++;
  275.         free_p(bp);
  276. #else
  277.         ip_recv(i_iface,&ip,bp,rxbroadcast);
  278. #endif
  279.         return 0;
  280.     }
  281.     /* Packet is not destined to us. If it originated elsewhere, count
  282.      * it as a forwarded datagram.
  283.      */
  284.     if(i_iface != NULLIF)
  285.         ipForwDatagrams++;
  286.  
  287.     /* Adjust the header checksum to allow for the modified TTL */        
  288.     ip.checksum += 0x100;
  289.     if((ip.checksum & 0xff00) == 0)
  290.         ip.checksum++;    /* end-around carry */
  291.  
  292.     /* Decrement TTL and discard if zero. We don't have to check
  293.      * rxbroadcast here because it's already been checked
  294.      */
  295.     if(--ip.ttl == 0){
  296.         /* Send ICMP "Time Exceeded" message */
  297.         icmp_output(&ip,bp,ICMP_TIME_EXCEED,0,NULLICMP);
  298.         ipInHdrErrors++;
  299.         free_p(bp);
  300.         return -1;
  301.     }
  302.     /* Look up target address in routing table */
  303.     if((rp = rt_lookup(ip.dest)) == NULLROUTE){
  304.         /* No route exists, return unreachable message (we already
  305.          * know this can't be a broadcast)
  306.          */
  307.         icmp_output(&ip,bp,ICMP_DEST_UNREACH,ICMP_HOST_UNREACH,NULLICMP);
  308.         free_p(bp);
  309.         ipOutNoRoutes++;
  310.         return -1;
  311.     }
  312.     rp->uses++;
  313.  
  314.     /* Check for output forwarding and divert if necessary */
  315.     iface = rp->iface;
  316.     if(iface->forw != NULLIF)
  317.         iface = iface->forw;
  318.  
  319.     /* Find gateway; zero gateway in routing table means "send direct" */
  320.     if(rp->gateway == 0)
  321.         gateway = ip.dest;
  322.     else
  323.         gateway = rp->gateway;
  324.  
  325.     if(strict && gateway != ip.dest){
  326.         /* Strict source routing requires a direct entry
  327.          * Again, we know this isn't a broadcast
  328.          */
  329.         icmp_output(&ip,bp,ICMP_DEST_UNREACH,ICMP_ROUTE_FAIL,NULLICMP);
  330.         free_p(bp);
  331.         ipOutNoRoutes++;
  332.         return -1;
  333.     }
  334.     prec = PREC(ip.tos);
  335.     del = ip.tos & DELAY;
  336.     tput = ip.tos & THRUPUT;
  337.     rel = ip.tos & RELIABILITY;
  338.  
  339. #ifdef FILTER
  340.     /*
  341.      *  If an output filter is specified on the output interface
  342.      *  then apply it.
  343.      */
  344.     if ( iface->outfilter && ip_filter( bp, &ip, iface->outfilter ) ) {
  345.         icmp_output(&ip,bp,ICMP_DEST_UNREACH,ICMP_HOST_UNREACH,NULLICMP);
  346.         free_p( bp );
  347.         return -1;
  348.     }
  349. #endif
  350.  
  351.     /* Tell demand dialer to open this link */
  352.     iface->dial_me = TRUE;
  353.  
  354.     if(ip.length <= iface->mtu){
  355.         /* Datagram smaller than interface MTU; put header
  356.          * back on and send normally.
  357.          */
  358.         if((tbp = htonip(&ip,bp,ckgood)) == NULLBUF){
  359.             free_p(bp);
  360.             return -1;
  361.         }
  362.         iface->ipsndcnt++;
  363.         return (*iface->send)(tbp,iface,gateway,prec,del,tput,rel);
  364.     }
  365.     /* Fragmentation needed */
  366.     if(ip.flags.df){
  367.         /* Don't Fragment set; return ICMP message and drop */
  368.         union icmp_args icmp_args;
  369.  
  370.         icmp_args.mtu = iface->mtu;
  371.         icmp_output(&ip,bp,ICMP_DEST_UNREACH,ICMP_FRAG_NEEDED,&icmp_args);
  372.         free_p(bp);
  373.         ipFragFails++;
  374.         return -1;
  375.     }
  376.     /* Create fragments */
  377.     offset = ip.offset;
  378.     mf_flag = ip.flags.mf;        /* Save original MF flag */
  379.     while(length != 0){        /* As long as there's data left */
  380.         int16 fragsize;        /* Size of this fragment's data */
  381.         struct mbuf *f_data;    /* Data portion of fragment */
  382.  
  383.         /* After the first fragment, should remove those
  384.          * options that aren't supposed to be copied on fragmentation
  385.          */
  386.         ip.offset = offset;
  387.         if(length + ip_len <= iface->mtu){
  388.             /* Last fragment; send all that remains */
  389.             fragsize = length;
  390.             ip.flags.mf = mf_flag;    /* Pass original MF flag */
  391.         } else {
  392.             /* More to come, so send multiple of 8 bytes */
  393.             fragsize = (iface->mtu - ip_len) & 0xfff8;
  394.             ip.flags.mf = 1;
  395.         }
  396.         ip.length = fragsize + ip_len;
  397.  
  398.         /* Duplicate the fragment */
  399.         dup_p(&f_data,bp,offset,fragsize);
  400.         if(f_data == NULLBUF){
  401.             free_p(bp);
  402.             ipFragFails++;
  403.             return -1;
  404.         }
  405.         /* Put IP header back on, recomputing checksum */
  406.         if((tbp = htonip(&ip,f_data,IP_CS_NEW)) == NULLBUF){
  407.             free_p(f_data);
  408.             free_p(bp);
  409.             ipFragFails++;
  410.             return -1;
  411.         }
  412.         /* and ship it out */
  413.         if((*iface->send)(tbp,iface,gateway,prec,del,tput,rel) == -1){
  414.             ipFragFails++;
  415.             free_p(bp);
  416.             return -1;
  417.         }
  418.         iface->ipsndcnt++;
  419.         ipFragCreates++;
  420.         offset += fragsize;
  421.         length -= fragsize;
  422.     }
  423.     ipFragOKs++;
  424.     free_p(bp);
  425.     return 0;
  426. }
  427. int
  428. ip_encap(bp,iface,gateway,prec,del,tput,rel)
  429. struct mbuf *bp;
  430. struct iface *iface;
  431. int32 gateway;
  432. int prec;
  433. int del;
  434. int tput;
  435. int rel;
  436. {
  437.     struct ip ip;
  438.  
  439.     dump(iface,IF_TRACE_OUT,CL_NONE,bp);
  440.     iface->rawsndcnt++;
  441.     iface->lastsent = secclock();
  442.  
  443.     if(gateway == 0L){
  444.         /* Gateway must be specified */
  445.         ntohip(&ip,&bp);
  446.         icmp_output(&ip,bp,ICMP_DEST_UNREACH,ICMP_HOST_UNREACH,NULLICMP);
  447.         free_p(bp);
  448.         ipOutNoRoutes++;
  449.         return -1;
  450.     }
  451.     /* Encapsulate in an IP packet from us to the gateway */
  452.     return ip_send(INADDR_ANY,gateway,IP_PTCL,0,0,bp,0,0,0);
  453. }
  454.  
  455. /* Add an entry to the IP routing table. Returns 0 on success, -1 on failure */
  456.  
  457. struct route *rt_add(
  458.     int32 target,                /* Target IP address prefix                             */
  459.     unsigned int bits,        /* Size of target address prefix in bits (0-32) */
  460.     int32 gateway,                /* Optional gateway to be reached via interface */
  461.     struct iface *iface,        /* Interface to which packet is to be routed     */
  462.     int32 metric,                /* Metric for this route entry                         */
  463.     int32 ttl,                    /* Lifetime of this route entry in sec             */
  464.     char private )                /* Inhibit advertising this entry ?                 */
  465. {
  466.     struct route *rp,**hp;
  467.     struct route *rptmp;
  468.     int32 gwtmp;
  469.  
  470.     if(iface == NULLIF)
  471.         return NULLROUTE;
  472.  
  473.     if(bits > 32)
  474.         bits = 32;        /* Bulletproofing */
  475.  
  476.     if(bits == 32 && ismyaddr(target))
  477.         return NULLROUTE;    /* Don't accept routes to ourselves */
  478.  
  479.     /* Mask off don't-care bits of target */
  480.     target &= ~0L << (32-bits);
  481.  
  482.     /* Encapsulated routes must specify gateway, and it can't be
  483.      *  ourselves
  484.      */
  485.     if(iface == &Encap && (gateway == 0 || ismyaddr(gateway)))
  486.         return NULLROUTE;
  487.  
  488.     Rt_cache.route = NULLROUTE;    /* Flush cache */
  489.  
  490.     /* Zero bits refers to the default route */
  491.     if(bits == 0){
  492.         rp = &R_default;
  493.     } else {
  494.         rp = rt_blookup(target,bits);
  495.     }
  496.     if(rp == NULLROUTE){
  497.         /* The target is not already in the table, so create a new
  498.          * entry and put it in.
  499.          */
  500.         rp = (struct route *)callocw(1,sizeof(struct route));
  501.         /* Insert at head of table */
  502.         rp->prev = NULLROUTE;
  503.         hp = &Routes[bits-1][hash_ip(target)];
  504.         rp->next = *hp;
  505.         if(rp->next != NULLROUTE)
  506.             rp->next->prev = rp;
  507.         *hp = rp;
  508.         rp->uses = 0;
  509.     }
  510.     rp->target = target;
  511.     rp->bits = bits;
  512.     rp->gateway = gateway;
  513.     rp->metric = metric;
  514.     rp->iface = iface;
  515.     rp->flags = private ? RTPRIVATE : 0;    /* Should anyone be told of this route? */
  516.     rp->timer.func = rt_timeout;  /* Set the timer field */
  517.     rp->timer.arg = (void *)rp;
  518.     set_timer(&rp->timer,ttl*1000L);
  519.     stop_timer(&rp->timer);
  520.     start_timer(&rp->timer); /* start the timer if appropriate */
  521.  
  522.     /* Check to see if this created an encapsulation loop */
  523.     gwtmp = gateway;
  524.     for(;;){
  525.         rptmp = rt_lookup(gwtmp);
  526.         if(rptmp == NULLROUTE)
  527.             break;    /* No route to gateway, so no loop */
  528.         if(rptmp->iface != &Encap)
  529.             break;    /* Non-encap interface, so no loop */
  530.         if(rptmp == rp){
  531.             rt_drop(target,bits);    /* Definite loop */
  532.             return NULLROUTE;
  533.         }
  534.         if(rptmp->gateway != 0)
  535.             gwtmp = rptmp->gateway;
  536.     }
  537.     return rp;
  538. }
  539.  
  540. /* Remove an entry from the IP routing table. Returns 0 on success, -1
  541.  * if entry was not in table.
  542.  */
  543. int
  544. rt_drop(target,bits)
  545. int32 target;
  546. unsigned int bits;
  547. {
  548.     register struct route *rp;
  549.  
  550.     Rt_cache.route = NULLROUTE;    /* Flush the cache */
  551.  
  552.     if(bits == 0){
  553.         /* Nail the default entry */
  554.         stop_timer(&R_default.timer);
  555.         R_default.iface = NULLIF;
  556.         return 0;
  557.     }
  558.     if(bits > 32)
  559.         bits = 32;
  560.  
  561.     /* Mask off target according to width */
  562.     target &= ~0L << (32-bits);
  563.  
  564.     /* Search appropriate chain for existing entry */
  565.     for(rp = Routes[bits-1][hash_ip(target)];rp != NULLROUTE;rp = rp->next){
  566.         if(rp->target == target)
  567.             break;
  568.     }
  569.     if(rp == NULLROUTE)
  570.         return -1;    /* Not in table */
  571.  
  572.     stop_timer(&rp->timer);
  573.     if(rp->next != NULLROUTE)
  574.         rp->next->prev = rp->prev;
  575.     if(rp->prev != NULLROUTE)
  576.         rp->prev->next = rp->next;
  577.     else
  578.         Routes[bits-1][hash_ip(target)] = rp->next;
  579.  
  580.     free((char *)rp);
  581.     return 0;
  582. }
  583. #ifdef    notdef
  584.  
  585. /* Compute hash function on IP address */
  586. static int16
  587. hash_ip(addr)
  588. register int32 addr;
  589. {
  590.     register int16 ret;
  591.  
  592.     ret = hiword(addr);
  593.     ret ^= loword(addr);
  594.     return (int16)(ret % HASHMOD);
  595. }
  596. #endif
  597. #ifndef    GWONLY
  598. /* Given an IP address, return the MTU of the local interface used to
  599.  * reach that destination. This is used by TCP to avoid local fragmentation
  600.  */
  601. int16
  602. ip_mtu(addr)
  603. int32 addr;
  604. {
  605.     register struct route *rp;
  606.     struct iface *iface;
  607.  
  608.     rp = rt_lookup(addr);
  609.     if(rp == NULLROUTE || rp->iface == NULLIF)
  610.         return 0;
  611.  
  612.     iface = rp->iface;
  613.     if(iface->forw != NULLIF)
  614.         return iface->forw->mtu;
  615.     else
  616.         return iface->mtu;
  617. }
  618. /* Given a destination address, return the IP address of the local
  619.  * interface that will be used to reach it. If there is no route
  620.  * to the destination, pick the first non-loopback address.
  621.  */
  622. int32
  623. locaddr(addr)
  624. int32 addr;
  625. {
  626.     register struct route *rp;
  627.     struct iface *ifp;
  628.  
  629.     if(ismyaddr(addr) != NULLIF)
  630.         return addr;    /* Loopback case */
  631.  
  632.     rp = rt_lookup(addr);
  633.     if(rp != NULLROUTE && rp->iface != NULLIF)
  634.         ifp = rp->iface;
  635.     else {
  636.         /* No route currently exists, so just pick the first real
  637.          * interface and use its address
  638.          */
  639.         for(ifp = Ifaces;ifp != NULLIF;ifp = ifp->next){
  640.             if(ifp != &Loopback && ifp != &Encap)
  641.                 break;
  642.         }
  643.     }
  644.     if(ifp == NULLIF || ifp == &Loopback)
  645.         return 0;    /* No dice */
  646.  
  647.     if(ifp == &Encap){
  648.         /* Recursive call - we assume that there are no circular
  649.          * encapsulation references in the routing table!!
  650.          * (There is a check at the end of rt_add() that goes to
  651.          * great pains to ensure this.)
  652.          */
  653.         return locaddr(rp->gateway);
  654.     }
  655.     if(ifp->forw != NULLIF)
  656.         return ifp->forw->addr;
  657.     else
  658.         return ifp->addr;
  659. }
  660. #endif
  661. /* Look up target in hash table, matching the entry having the largest number
  662.  * of leading bits in common. Return default route if not found;
  663.  * if default route not set, return NULLROUTE
  664.  */
  665. struct route *
  666. rt_lookup(target)
  667. int32 target;
  668. {
  669.     register struct route *rp;
  670.     int bits;
  671.     int32 tsave;
  672.     int32 mask;
  673.  
  674.     /* Examine cache first */
  675.     if(target == Rt_cache.target && Rt_cache.route != NULLROUTE)
  676.         return Rt_cache.route;
  677.  
  678.     tsave = target;
  679.  
  680.     mask = ~0;    /* All ones */
  681.     for(bits = 31;bits >= 0; bits--){
  682.         target &= mask;
  683.         for(rp = Routes[bits][hash_ip(target)];rp != NULLROUTE;rp = rp->next){
  684.             if(rp->target == target){
  685.                 /* Stash in cache and return */
  686.                 Rt_cache.target = tsave;
  687.                 Rt_cache.route = rp;
  688.                 return rp;
  689.             }
  690.         }
  691.         mask <<= 1;
  692.     }
  693.     if(R_default.iface != NULLIF){
  694.         Rt_cache.target = tsave;
  695.         Rt_cache.route = &R_default;
  696.         return &R_default;
  697.     } else
  698.         return NULLROUTE;
  699. }
  700. /* Search routing table for entry with specific width */
  701. struct route *
  702. rt_blookup(target,bits)
  703. int32 target;
  704. unsigned int bits;
  705. {
  706.     register struct route *rp;
  707.  
  708.     if(bits == 0){
  709.         if(R_default.iface != NULLIF)
  710.             return &R_default;
  711.         else
  712.             return NULLROUTE;
  713.     }
  714.     /* Mask off target according to width */
  715.     target &= ~0L << (32-bits);
  716.  
  717.     for(rp = Routes[bits-1][hash_ip(target)];rp != NULLROUTE;rp = rp->next){
  718.         if(rp->target == target){
  719.             return rp;
  720.         }
  721.     }
  722.     return NULLROUTE;
  723. }
  724. /* Scan the routing table. For each entry, see if there's a less-specific
  725.  * one that points to the same interface and gateway. If so, delete
  726.  * the more specific entry, since it is redundant.
  727.  */
  728. void
  729. rt_merge(trace)
  730. int trace;
  731. {
  732.     int bits,i,j;
  733.     struct route *rp,*rpnext,*rp1;
  734.  
  735.     for(bits=32;bits>0;bits--){
  736.         for(i = 0;i<HASHMOD;i++){
  737.             for(rp = Routes[bits-1][i];rp != NULLROUTE;rp = rpnext){
  738.                 rpnext = rp->next;
  739.                 for(j=bits-1;j >= 0;j--){
  740.                     if((rp1 = rt_blookup(rp->target,j)) != NULLROUTE
  741.                      && rp1->iface == rp->iface
  742.                      && rp1->gateway == rp->gateway){
  743.                         if(trace > 1)
  744.                             printf("merge %s %d\n",
  745.                              inet_ntoa(rp->target),
  746.                              rp->bits);
  747.                         rt_drop(rp->target,rp->bits);
  748.                         break;
  749.                     }
  750.                 }
  751.             }
  752.         }
  753.     }
  754. }
  755.